// Created by WXX on 2022/1/29 19:07
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

/**
 * 执行用时：308 ms, 在所有 C++ 提交中击败了44.00%的用户
 * 内存消耗：120.2 MB, 在所有 C++ 提交中击败了26.40%的用户
 */
#define x first
#define y second

typedef pair<int, int> PII;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

class Solution {
public:
    int n, m;
    vector<vector<int>> g;
    vector<vector<int>> dist;
    queue<PII> q;

    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {

        n = isWater.size(), m = isWater[0].size();
        g = vector<vector<int>>(n, vector<int>(m, 1e9));
        dist = vector<vector<int>>(n, vector<int>(m, -1));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (isWater[i][j]) {
                    g[i][j] = 0;
                    q.push({i, j});
                    dist[i][j] = 0;
                }

        bfs();

        return g;
    }

    void bfs() {
        while (q.size()) {
            auto t = q.front();
            q.pop();

            for (int k = 0; k < 4; k++) {
                int x = t.x + dx[k], y = t.y + dy[k];
                if (x >= 0 && x < n && y >= 0 && y < m && dist[x][y] == -1) {
                    q.push({x, y});
                    dist[x][y] = dist[t.x][t.y] + 1;
                    g[x][y] = min(g[x][y], dist[x][y]);
                }
            }
        }
    }
};

void OutputBasicArray2D(vector<vector<int>> nums) {

    cout << "[";
    for (int i = 0; i < nums.size(); i++) {
        if (i > 0 && i < nums.size()) cout << ' ';
        cout << "[";
        for (int j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ", ";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ", " << endl;
    }
    cout << "]" << endl;
}

int main() {

    vector<vector<int>> g = {
            {0, 0, 1},
            {1, 0, 0},
            {0, 0, 0}
    };
    OutputBasicArray2D(Solution().highestPeak(g));

    return 0;
}
